<h2>Problem 150</h2>
<div style="color:#666;font-size:80%;">13 April 2007</div><br />
<div class="problem_content">
<p>In a triangular array of positive and negative integers, we wish to find a sub-triangle such that the sum of the numbers it contains is the smallest possible.</p>
<p>In the example below, it can be easily verified that the marked triangle satisfies this condition having a sum of <img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' />42.</p>
<div style="text-align:center;">
<img src="http://projecteuler.net/project/images/p_150.gif" border="0" alt="" />
</div>
<p>We wish to make such a triangular array with one thousand rows, so we generate 500500 pseudo-random numbers <span style="font-style: italic">s<img src="" style="display:none;" alt="_(" /><sub>k</sub><img src="" style="display:none;" alt=")" /></span> in the range <img src='images/symbol_plusmn.gif' width='11' height='11' alt='&plusmn;' border='0' style='vertical-align:middle;' />2<img src="" style="display:none;" alt="^(" /><sup>19</sup><img src="" style="display:none;" alt=")" />, using a type of random number generator (known as a Linear Congruential Generator) as follows:</p>
<p style="margin-left:50px;"><span style="font-style: italic">t</span> := 0
<br />
for k = 1 up to k = 500500:
<br />
&nbsp; &nbsp; <span style="font-style: italic">t</span> := (615949*<span style="font-style: italic">t</span> + 797807) modulo 2<img src="" style="display:none;" alt="^(" /><sup>20</sup><img src="" style="display:none;" alt=")" />
<br />
&nbsp; &nbsp; <span style="font-style: italic">s<img src="" style="display:none;" alt="_(" /><sub>k</sub><img src="" style="display:none;" alt=")" /></span> := <span style="font-style: italic">t</span><img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' />2<img src="" style="display:none;" alt="^(" /><sup>19</sup><img src="" style="display:none;" alt=")" /></p>
<p>Thus: <span style="font-style: italic">s<img src="" style="display:none;" alt="_(" /><sub>1</sub><img src="" style="display:none;" alt=")" /></span> = 273519, <span style="font-style: italic">s<img src="" style="display:none;" alt="_(" /><sub>2</sub><img src="" style="display:none;" alt=")" /></span> = <img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' />153582, <span style="font-style: italic">s<img src="" style="display:none;" alt="_(" /><sub>3</sub><img src="" style="display:none;" alt=")" /></span> = 450905 etc</p>
<p>Our triangular array is then formed using the pseudo-random numbers thus:</p>
<div style="text-align:center;font-style: italic;">
s<img src="" style="display:none;" alt="_(" /><sub>1</sub><img src="" style="display:none;" alt=")" />
<br />
s<img src="" style="display:none;" alt="_(" /><sub>2</sub><img src="" style="display:none;" alt=")" />&nbsp; s<img src="" style="display:none;" alt="_(" /><sub>3</sub><img src="" style="display:none;" alt=")" />
<br />
s<img src="" style="display:none;" alt="_(" /><sub>4</sub><img src="" style="display:none;" alt=")" />&nbsp; s<img src="" style="display:none;" alt="_(" /><sub>5</sub><img src="" style="display:none;" alt=")" />&nbsp; s<img src="" style="display:none;" alt="_(" /><sub>6</sub><img src="" style="display:none;" alt=")" />&nbsp; 
<br />
s<img src="" style="display:none;" alt="_(" /><sub>7</sub><img src="" style="display:none;" alt=")" />&nbsp; s<img src="" style="display:none;" alt="_(" /><sub>8</sub><img src="" style="display:none;" alt=")" />&nbsp; s<img src="" style="display:none;" alt="_(" /><sub>9</sub><img src="" style="display:none;" alt=")" />&nbsp; s<img src="" style="display:none;" alt="_(" /><sub>10</sub><img src="" style="display:none;" alt=")" />
<br />
...
</div>
<p>Sub-triangles can start at any element of the array and extend down as far as we like (taking-in the two elements directly below it from the next row, the three elements directly below from the row after that, and so on).
<br />
The &quot;sum of a sub-triangle&quot; is defined as the sum of all the elements it contains.
<br />
Find the smallest possible sub-triangle sum.</p>
</div><br />
